#include <iostream>
#include <vector>
using namespace std;

class Solution {
        int most_hourse(vector<int> &nums, int ability)
        {
                int n = nums.size();
                if(n == 1){
                        return ability >= nums[0] ? 1 : 0;
                }

                if(n == 2){
                        return ability >= min(nums[0], nums[1]) ? 1 : 0;
                }

                int dp[n];
                dp[0] = ability >= nums[0] ? 1 : 0;
                dp[1] = ability >= min(nums[0], nums[1]) ? 1 : 0;
                for(int i = 2; i < n; i++){
                        dp[i] = max(dp[i - 1], (ability >= nums[i] ?  1 : 0) + dp[i - 2]);
                }
                return dp[n - 1];
        }
    public:
	int minCapability(vector<int> &nums, int k)
	{
                int n = nums.size(), l = nums[0], r = l;
                for(int i = 1; i < n; i++){
                        l = min(l, nums[i]);
                        r = max(r, nums[i]);
                }
                int m, ans = l;
                while(l <= r){
                        m = (l + r)/2;
                        if(most_hourse(nums, m) >= k){
                                ans = m;
                                r = m - 1;
                        }else{
                                l = m + 1;
                        }
                }
                return ans;
	}
};

int main()
{
	vector<int> nums = { 7, 3, 9, 5 };
	int k = 2;
        cout<<Solution().minCapability(nums, k)<<endl;
	return 0;
}